/**
 * FileName: LOffer38
 * Author:   powersi
 * Date:     2021/3/13 13:32
 * Description:
 */
package com.zm.demo.core.leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.stream.Stream;

/**
 * Description: 
 * Author:      powersi
 * Date:        2021/3/13 13:32
 */
public class LOffer38 {

    public static void main(String[] args) {
        new LOffer38().permutation("aab");
    }
    public String[] permutation(String s) {
        int length = s.length();
        List<String> list = new ArrayList<>();
        calc(s, list, new StringBuilder(),length);
        return list.toArray(new String[list.size()]);
    }

    int i=0;
    /**
     * abc acb bac bca cab cba
     * @param s
     */
    private void calc(String s, List<String> list, StringBuilder sb, int length) {
        if (sb.length() == length){
            if (list.contains(sb.toString())){
              return;
            }
            list.add(sb.toString());
            return;
        }
        for (int j = 0; j < s.length(); j++) {
            StringBuilder sb1 = new StringBuilder();
            sb1.append(sb).append(s.charAt(j));
            calc(remove(s,j), list, sb1, length);
        }
    }

    String remove(String s, int index){
        StringBuilder sb = new StringBuilder(s);
        sb.replace(index,index+1,"");
        return sb.toString();
    }
}
